import java.util.ArrayList;
import java.util.Queue;
import java.util.Stack;

/*
 * @lc app=leetcode.cn id=224 lang=java
 *
 * [224] 基本计算器
 */

// @lc code=start
class Solution {
    public int calculate(String s) {
        char[] strings = s.toCharArray();
        ArrayList<String> list = getArrayList(strings);
        Queue<String> queue =  middleTransSuffix(list);
        if ( queue.size() == 1){
            return Integer.parseInt(queue.peek());
        }else 
           return getresult(queue);
    }
    public ArrayList<String> getArrayList(char[] chs){
        ArrayList<String> list = new ArrayList<String>();
        String str = "";
        for ( char ch : chs){
            if ( isCharDigit(ch) ){
                str += ch; 
            }else if (ch != ' ' || !(str.equals(""))){
                if ( str.equals("") ){
                    list.add(ch+"");
                }else {
                    list.add(str);
                    if ( ch != ' ')
                        list.add(ch+"");
                    str = "";
                }
            }
        }
        if ( !(str.equals(""))){
            list.add(str);
        }
        return list;
    }
    public  boolean isCharDigit(char s){
        return Character.isDigit(s);
    }

    public Queue<String> middleTransSuffix(ArrayList<String> arrayList){
        Queue<String> queue = new LinkedList<>();
        Stack<String> stack = new Stack<>();
        for ( String str: arrayList){
            // System.out.println(str);
            if ( isDigit(str) ){
                queue.add(str);
            }else {
                if (stack.isEmpty() || (stack.size() == 1 && stack.peek().equals("("))){
                    if ( !(str.equals(")")) )
                        stack.push(str);
                    else 
                        stack.pop();
                }else if (str.equals(")")){
                    //弹出栈内的元素直到遇到"("
                    while ( true ) {
                        String pop = stack.pop();
                        if (!(pop.equals("(")))
                            queue.add(pop);
                        else
                            break;
                    }
                    //判断优先级大小
                }else if ( str.equals("-") || str.equals("+")){
                    //将优先级比str高的运算符放入队列中
                    while ( !(stack.isEmpty()) && !(stack.peek().equals("(")) ){
                        queue.add(stack.pop());
                    }
                    //str入栈
                    stack.push(str);
                }
                else {
                    stack.push(str);
                }
            }
        }
        while (!(stack.isEmpty())){
            queue.add(stack.pop());
        }
        return queue;
    }
    public boolean isDigit(String str){
        for (int i = str.length();--i>=0;){  
            if (!Character.isDigit(str.charAt(i))){
                return false;
            }
        }
        return true;
    }
    public int getresult(Queue queue){
        int result = 0;
        Stack<Object> stack = new Stack<Object>();
        String str = null;
        while (!(queue.isEmpty())){
           str = (String) queue.poll();
            if ( isDigit(str) ){
                Integer i = Integer.parseInt(str);
                System.out.println(i);
                stack.push(i);
            }else {
                Integer num1 = (Integer) stack.pop();
                Integer num2 = (Integer) stack.pop();
                if ( str.equals("+") ){
                    stack.push(num1+num2);
                }else {
                    stack.push(num2-num1);
                }
            }
        }
        result = (Integer) stack.pop();
        return result;
    }
}
// @lc code=end

